/**
 * 实现双向循环带头链表
 */
#pragma once
#include <iostream>
#include <unistd.h>
namespace myList
{
    // 节点属性
    template <class T>
    struct ListNode
    {
    public:
        ListNode()
            : _value(T()), _prev(nullptr), _next(nullptr)
        {
        }
        ListNode(const T &value)
            : _value(value), _prev(nullptr), _next(nullptr)
        {
        }
        ListNode(const ListNode<T> &another)
        {
            _value = another._value;
            _prev = another._prev;
            _next = another._next;
        }
        ~ListNode()
        {
            _prev = nullptr;
            _next = nullptr;
        }

        T _value;
        ListNode *_prev;
        ListNode *_next;
    };

    // 迭代器
    template <class T>
    class Iterator
    {
    public:
        Iterator(ListNode<T> *node)
            : _it(node)
        {
        }
        Iterator<T> operator++()
        {
            _it = _it->_next;
            return _it;
        }
        Iterator<T> operator--()
        {
            _it = _it->_prev;
            return _it;
        }
        T &operator*()
        {
            return _it->_value;
        }

        bool operator!=(const Iterator<T> &another)
        {
            return _it != another._it;
        }

        ListNode<T> *_it;
    };

    template <class T>
    class List
    {
    public:
        using iterator = Iterator<T>;
        using node = ListNode<T>;

    public:
        List()
            : _begin(nullptr), _end(nullptr), _head(nullptr)
        {
            _head = new node();
            _head->_prev = _head;
            _head->_next = _head;
            _end = _head;
        }
        ~List()
        {
            if (_begin != nullptr)
            {
                node *cur = _begin;
                node *next = _begin->_next;
                while (next != _end)
                {
                    delete cur;
                    cur = next;
                    next = next->_next;
                }
                delete cur;
            }
            delete _end;
        }

        void insert(iterator pos, const T &value)
        {
            node *newnode = new node(value);
            // 第一次插入
            if (_head->_next == _head)
            {
                _head->_next = newnode;
                newnode->_prev = _head;

                _head->_prev = newnode;
                newnode->_next = _head;
            }
            else
            {
                newnode->_next = pos._it;
                newnode->_prev = pos._it->_prev; 
                pos._it->_prev->_next = newnode;
                pos._it->_prev = newnode;
            }
            _begin = _head->_next;
        }
        void push_back(const T &value) { insert(end(), value); }
        void push_front(const T &value) { insert(begin(), value); }

        void erase(iterator pos)
        {
            assert(pos != _end);
            assert(size() > 0);

            pos._it->_prev->_next = pos._it->_next;
            pos._it->_next->_prev = pos._it->_prev;
            delete pos._it;
            _begin = _head->_next;
        }
        void pop_back() { erase(iterator(_end->_prev)); }
        void pop_front() { erase(begin()); }

        iterator begin() { return iterator(_begin); }
        iterator end() { return iterator(_end); }

        int size()
        {
            node* cur = _begin;
            int size = 0;
            while(cur != _end)
            {
                ++size;
                cur = cur->_next;
            }
            return size;
        }

        bool empty()
        {
            return _begin == _end;
        }
    private:
        node *_begin; // 链表起始节点
        node *_end;   // 链表终止节点的下一个节点
        node *_head;  // 链表的头节点
    };
}
